817C - Really Big Numbers - CodeForces Solution


binary search brute force dp math *1600

Please click on ads to support us..

Python Code:

n, s = map(int, input().split())
dem = max(0, n - (s + 162) + 1)
for x in range(s, min(n, s+161) + 1):
    if x - sum([int(u) for u in str(x)]) >= s:
        dem += 1
print(dem)

C++ Code:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int sumOfDig(ll num)
{
    int sum = 0;
    while (num)
    {
        sum += num % 10;
        num /= 10;
    }
    return sum;
}
ll diff(ll num)
{
    return num - sumOfDig(num);
}
bool isValid(ll num, ll s)
{
    return s <= diff(num);
}
int main()
{
    ll n, s;
    cin >> n >> s;

    ll l, r, m;
    l = 0;
    r = n;
    ll ans = -1;
    while (l <= r)
    {
        m = l + (r - l) / 2;

        if (isValid(m, s))
        {
            r = m - 1;
            ans = m;
        }
        else
        {
            l = m + 1;
        }
    }

    printf("%lld", n < n - ans + 1 ? 0 : n - ans + 1);

    return 0;
}


Comments

Submit
0 Comments
More Questions

799A - Carrot Cakes
1569B - Chess Tournament
1047B - Cover Points
1381B - Unmerge
1256A - Payment Without Change
908B - New Year and Buggy Bot
979A - Pizza Pizza Pizza
731A - Night at the Museum
742A - Arpa’s hard exam and Mehrdad’s naive cheat
1492A - Three swimmers
1360E - Polygon
1517D - Explorer Space
1230B - Ania and Minimizing
1201A - Important Exam
676A - Nicholas and Permutation
431A - Black Square
474B - Worms
987B - High School Become Human
1223A - CME
1658B - Marin and Anti-coprime Permutation
14B - Young Photographer
143A - Help Vasilisa the Wise 2
320A - Magic Numbers
1658A - Marin and Photoshoot
514A - Chewbaсca and Number
382A - Ksenia and Pan Scales
734B - Anton and Digits
1080A - Petya and Origami
1642D - Repetitions Decoding
1440A - Buy the String